/**
*  Author: Magnus Hemmer Pihl
*  Student number: 5452
*
*  Assignment 2
*  16/9-2007
**/

#include <cstdlib>
#include <iostream>
#ifndef INITIAL_SIZE
#define INITIAL_SIZE 2
#endif

using namespace std;

//Creates a list containing a dynamic number of elements.
//The list performs automatic resizing and rearranging.
//See List.cpp for per-method descriptions.
template <typename varType>
class List
{
private:
    int size;			//Actual size (number of positions) in the array
    varType *arr;		//The array containing data
    int length;			//Number of initialized elements in the array

    //Expands the capacity of the list by creating a new, larger array and re-referencing.
    //Array capacity is always doubled.
    void expand()
    {
        varType *original = arr;
        int originalSize = size;
        size *= 2;
        arr = new varType[size];
        for(int i=0; i<originalSize; i++)
            arr[i] = original[i];
        delete [ ] original;
        original = NULL;
    }

    //Rearranges ("defragments") elements so that there are no empty spaces in the array
    // between data-holding spaces.
    void rearrange()
    {
        for(int i=0; i<size; i++)
            if(arr[i] == NULL)
            {
                arr[i] = arr[i+1];
                arr[i+1] = NULL;
            }
    }
    
    //Shifts all elements of the array forward one position, starting with given position 'pos'.
    //This is useful if you wish to insert data on a previously occupied position.
    void shiftArray(int pos)
    {
        if(size <= length)
            expand();
        for(int i=length-1; i>=pos; i--)
            arr[i+1] = arr[i];
        arr[pos] = NULL;
    }

public:
    //Constructor. Initialized variables.
    List()
    {
        size = INITIAL_SIZE;
        arr = new varType[size];
        length = 0;
    }

    //Copy constructor.
    List(const List &data)
    {
        size = INITIAL_SIZE;
        arr = new varType[size];
        length = 0;
        for(int i=0; i<data.length; i++)
            this->push(data.arr[i]);
    }

    //Destructor. Releases memory held by array.
    ~List()
    {
        delete [] arr;
        arr = NULL;
    }

    //Inserts data 'val' at position 'pos'.
    //This will shift forward any previous data in this position, and all data following it.
    void insert(varType val, int pos)
    {
        if(pos >= 0 && pos <= length)
        {
            shiftArray(pos);
            arr[pos] = val;
            length++;
        }
    }

    //Erases data in position 'pos'.
    //This will cause the array to be rearranged, shifting any data beyond 'pos' back one position.
    void erase(int pos)
    {
        if(pos >= 0 && pos < length)
        {
            arr[pos] = NULL;
            length--;
            rearrange();
        }
    }

    //Inserts data 'val' onto the first unused position (the end) of the list.
    void push(varType val)
    {
        insert(val, length);
    }
    
    //Returns and deletes the data in the last position of the list.
    varType pop()
    {
        varType val = arr[length-1];
        erase(length-1);
        return val;
    }
    
    //Returns the length (used slots - NOT array capacity!) of the list.
    int getSize()
    {
        return length;
    }

    //Deletes all data in the list and resizes the array to its initial size.
    void clear()
    {
        delete [] arr;
        size = INITIAL_SIZE;
        length = 0;
        arr = new varType[size];
    }
    
    //Returns 'true' if the list contains no data, or 'false' if it does.
    bool empty()
    {
        if(arr[0] == NULL)
            return true;
        return false;
    }

    //Returns data held at position 'pos'.
    varType & at(int pos)
    {
        if(pos <0 || pos >= length)
        pos = pos%length;
        return *(arr + pos);
    }

    //Swaps the positions of two elements in the List.
    void swap(int a, int b)
    {
        if(a < size && b < size && a!=b)
        {
            varType temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

    //Reverses the order of the list.
    void reverse()
    {
        int i = 0;
        int j = length-1;
        while(i<j)
        {
            swap(i, j);
            i++;
            j--;
        }
    }

    //Calls the default sorting algorithm (QuickSort) on the list.
    void sort()
    {
        quickSort(0, length-1);
    }

    //Calls the QuickSort sorting function on the entire List.
    void quickSort()
    {
        quickSort(0, length-1);
    }

    //Sorts the List in ascending order, using the QuickSort algorithm.
    void quickSort(int start, int end)
    {
        int i = start;      //Left-end index
        int j = end;        //Right-end index
        if(end-start >= 1)  //Array has more than 1 element
        {
            int pivot = arr[start]; //Choose first index as pivot
            while(j > i)    //Make sure the two indices don't pass each other
            {
                while(arr[i] <= pivot && i<=end && j>i)  //Find the first position (from left) that is larger than the pivot
                    i++;
                while(arr[j] > pivot && j>=start && j>=i)  //Find the first position (from right) that is smaller than the pivot
                    j--;
                if(j > i)
                    swap(i,j);  //If the indices haven't crossed, value at k must be smaller than value at i, so swap
                //this->print();
            }
            swap(start, j);     //Swap start position with right-most position that is smaller than the pivot

            quickSort(start, j-1);   //Sort left partition
            quickSort(j+1, end);     //Sort right partition
        }
        else
            return;
    }

    //Sorts the List in ascending order, using the SelectionSort algorithm.
    void selectionSort()
    {
        int i, j, min;

        for(i=0; i < length -1; i++)
        {
            min = i;
            for(j=i+1; j < length; j++)
                if(arr[j] < arr[min])
                    min = j;
            swap(min, i);
            //this->print();
        }
    }

    //Operator overload for assignment. Clears current list and sets it to be equivalent to given data.
    const List & operator=(const List &data)
    {
        this->clear();
        for(int i=0; i < data.length; i++)
            this->push(data.arr[i]);
        return *this;
    }
    
    //Operator overload for []. Equivalent of List::at(int pos).
    varType & operator[](int pos)
    {
        while(pos >= size)
            expand();
        if(pos >= length)
            length++;
        return arr[pos];
    }

    //Operator overload for []. Const version.
    const varType & operator[](int pos) const
    {
        return arr[pos];
    }

    //Returns a new list containing the appended data of this list, and given list 'data'.
    List &operator+(const List &data)
    {
        List *result = new List();
        for(int i=0; i < this->length; i++)
            result->push(this->arr[i]);
        for(int i=0; i < data.length; i++)
            result->push(data.arr[i]);
        return *result;
    }

    //Appends the content of list 'data' onto this list.
    List &operator+=(const List &data)
    {
        for(int i=0; i < data.length; i++)
            this->push(data.arr[i]);
        return *this;
    }

    //Checks for equality of given list 'data' and this list.
    bool operator==(const List &data)
    {
        if(this->length != data.length)
            return false;
        for(int i=0; i<this->length; i++)
            if(this->arr[i] != data.arr[i])
                return false;
        return true;
    }

    //See List::operator==
    bool operator!=(const List &data)
    {
        return !(this->operator==(data));
    }
    
    //Overload for output stream.
    friend ostream &operator<<(ostream &os, const List &data)
    {
        os << "{";
        for(int i=0; i<data.length; i++)
        {
            os << data.arr[i];
            if(i+1 < data.length)
                os << ", ";
        }
        os << "}";

        return os;
    }

    //Prints the contents of the list to the console, similar to &operator<<.
    void print()
    {
        cout << "{";
        for(int i=0; i<this->length; i++)
        {
            cout << this->arr[i];
            if(i+1 < this->length)
                cout << ", ";
        }
        cout << "}\n";
    }
};